package com.sk.leetcode.arithmetic;

import java.util.ArrayList;
import java.util.List;

/**
 * 给定一个非空二叉树，返回其最大路径和。
 * 本题中，路径被定义为一条从树中任意节点出发，达到任意节点的序列。该路径至少包含一个节点，且不一定经过根节点。
 */
public class Test124 {
    private static int max = Integer.MIN_VALUE;

    public static void main(String[] args) {
        //Integer[] h = {0, -9, -20, 600, 400, -15, 700, -1, null, -3, -9, -67, -1, -2, null};
        Integer[] h = {0};
        List<TreeNode> nodes = suan(h);

        int max = maxPathSum(nodes.get(0));
        System.out.println(max);
    }

    /**
     * 将数组转换成tree
     */
    public static List<TreeNode> suan(Integer[] h) {
        TreeNode node = new TreeNode(h[0]);
        int le = (h.length + 1) / 2;
        int he = (int) (Math.log(le) / Math.log(2));
        List<TreeNode> list = new ArrayList<>();
        list.add(node);
        int index = 0;
        for (int i = 1; i <= he; i++) {
            int n = (int) Math.pow(2, i - 1);
            int num = (int) Math.pow(2, i) - 1;

            for (int j = 0; j < n; j++) {
                TreeNode node1 = list.get(index);
                if(node1 != null) {
                    if(h[num + j * 2] != null) {
                        TreeNode treel = new TreeNode(h[num + j * 2]);
                        node1.left = treel;
                        list.add(treel);
                    }
                    if(h[num + j * 2 + 1] != null) {
                        TreeNode treer = new TreeNode(h[num + j * 2 + 1]);
                        node1.right = treer;
                        list.add(treer);
                    }
                }

                index++;
            }
        }
        return list;
    }

    private static int jisuan(TreeNode root) {
        max = Integer.MIN_VALUE;
        int ret = root.val;
        if(root.left == null && root.right == null) {
            if(ret > max) {
                max = ret;
            }
            return ret;
        }
        int l = 0, r = 0;
        if(root.left != null) {
            l = jisuan(root.left);
            if(l < 0) {
                l = 0;
            }
        }
        if(root.right != null) {
            r = jisuan(root.right);
            if(r < 0) {
                r = 0;
            }
        }

        int m = ret + l + r;
        if(m > max) {
            max = m;
        }
        if(l > r) {
            return ret + l;
        }
        return ret + r;
    }

    public static int maxPathSum(TreeNode root) {
        jisuan(root);
        return max;
    }
}

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;

    TreeNode(int x) {
        val = x;
    }
}